The present invention is directed to a peer-to-peer load balancing system which is implemented in plural network servers. In particular, the invention is directed to a computer-executable module for use in network servers which enables each server to distribute loads among its peers based on a load currently being processed in each server and/or contents of the network requests. The invention has particular utility in connection with World Wide Web servers, but can be used with other servers as well, such as CORBA servers, ORB servers, FTP servers, SMTP servers, and Java servers.
Network systems, such as the World Wide Web (hereinafter "WWW"), utilize servers to process requests for information. Problems arise, however, if one server becomes overloaded with requests. For example, if a server becomes overloaded, it may be unable to receive new requests, may be slow to process the requests that it has already received, and may yield server errors.
Load balancing was developed to address the foregoing problems in the art. Briefly, load balancing involves distributing requests among plural servers (e.g., different servers on a Web site) in order to ensure that any one server does not become unduly burdened.
One conventional load balancing technique involves the use of a domain name server (hereinafter "DNS"), in particular a "round-robin" DNS. This device, which typically operates on the network, is responsible for resolving uniform resource locators or "URLs" (e.g., "www.foo.com") to specific IP addresses (e.g., 111.222.111.222). In this regard, a Web site having several servers may operate under a single URL, although each server is assigned a different IP address. A round-robin DNS performs load balancing by routing requests to these servers in sequential rotation based on their IP addresses.
While round-robin DNSs can coarsely distribute loads among several servers, they have several drawbacks. For example, not all requests for connection to a Web site are necessarily received by a round-robin DNS. Rather, many requests will have been previously "resolved" by a DNS local to the requester and remote from the Web site (i.e., a "a remote DNS") or by the requester (i.e., the computer that issued the request on the WWW). In these cases, resolution is based on an address which has been cached in the remote DNS or the requestor, rather than by sequential rotation provided by the Web site's round-robin DNS. Due to this caching, load balancing may not be achieved to a satisfactory degree.
DNS-based load balancing techniques have another significant drawback. In the event that a Web server fails (i.e., the Web server goes off-line), the Web site has no real-time mechanism by which to reroute requests directed to that server (e.g., by a remote DNS). Thus, a remote DNS with caching capabilities could continue to route requests to a failed server for hours, or even days, after the failure has occurred. As a result, a user's connection would be denied with no meaningful error message or recovery mechanism. This situation is unacceptable, particularly for commercial Web sites.
As an alternative to the DNS-based load balancing techniques described above, some vendors have introduced dedicated load balancing hardware devices into their systems. One such system includes a device, called a proxy gateway, which receives all network requests and routes those requests to appropriate Web servers. In particular, the proxy gateway queries the servers to determine their respective loads and distributes network requests accordingly. Responses from the servers are routed back to the network through the proxy gateway. Unlike the DNS-based schemes, all requests resolve to the IP address of the proxy server, thereby avoiding the risk that remote DNS caching or failed servers will inadvertently thwart access to the site.
While proxy gateways address some of the fundamental problems of load balancing described above, they also have several drawbacks. For example, proxy gateways add latency in both the "request" direction and the "response" direction. Moreover, since the proxy gateway is, for all intents and purposes, the only way into or out of a Web site, it can become a bottleneck that limits the capacity of that site to the capacity of the proxy gateway. Moreover, the proxy gateway is also a single point of failure, since its failure alone will prevent access to the Web site.
An IP redirector is a device similar to a proxy gateway which also performs load balancing. Like a proxy gateway, an IP redirector serves as a hub that receives and routes requests to appropriate servers based on the servers' loads. IP redirectors are different from proxy gateways in that IP redirectors do not handle responses to requests, but rather let those responses pass directly from the assigned Web servers to the requesters. However, IP redirectors suffer from many of the same drawbacks of the proxy gateways described above, particularly insofar as limiting the capacity of the Web site and preventing access to it as a result of failure of the IP redirector.
Dedicated load balancers, such as proxy gateways and IP redirectors, also have drawbacks related to sensing loads in different Web servers. Using current technologies, a server can become busy in a matter of milliseconds. A load balancer, however, can only query various servers so often without creating undesirable overhead on the network and in the servers themselves. As a result, such load balancers often must rely on "old" information" to make load balancing decisions. Load balancing techniques which use this "old" information are often ineffective, particularly in cases where such information has changed significantly.
Dedicated load balancers, such as proxy gateways and IP redirectors, also have problems when it comes to electronic commerce transactions. In this regard, electronic commerce transactions are characterized by multiple sequential requests from a single client, where each subsequent request may need to refer to state information provided in an earlier request. Examples of this state information include passwords, credit card numbers, and purchase selections.
Problems with electronic commerce arise because an entire transaction must be serviced by one of plural network servers, since only that one server has the original state information. A load balancer therefore must identify the first request of a stateful transaction and keep routing requests from that requester to the same server for the duration of the transaction. However, it is impossible for the load balancer to know exactly where a transaction begins or ends, since the information in the request providing such indications may be encrypted (e.g., scrambled) when it passes through the dedicated load balancer. In order to maintain an association between one requestor and one server, dedicated load balancers therefore use a mechanism referred to as a "sticky timer". More specifically, the load balancer infers which request may be the start of a stateful transaction and then sets a "sticky timer" of arbitrary duration (e.g., 20 minutes) which routes all subsequent requests from the same requestor to the same Web server, and which renews the "sticky timer" with each subsequent request. This method is easily bypassed and may unnecessarily defeat the load balancing feature.
Thus, there exists a need for a load balancing technique which is able to provide more accurate load balancing than the techniques described above, which is able to perform accurate load balancing despite cached server addresses or "maintained" Web browser addresses, which is not a significant bottleneck or source of single point failure, and which is able to maintain the association between a client and a server in order to preserve state information required to complete an electronic commerce transaction.